package org.basis.algorithm.lru;

import java.util.HashMap;
import java.util.Map;

/**
 * lru算法自定义实现
 * lru : 最不常使用淘汰算法，即淘汰最久未使用的数据
 *
 * @author Mr_wenpan@163.com 2022/01/02 15:24
 */
public class MyLru {

    /**
     * map用于记录key在链表中的位置，使得查找一个节点时间复杂度变为O（1）
     */
    private Map<String, Node> map;
    /**
     * 容量
     */
    private int limit;
    /**
     * 链表头节点
     */
    private Node head = null;
    /**
     * 链表尾节点
     */
    private Node tail = null;

    public MyLru(int limit) {
        this.limit = limit;
        map = new HashMap<>();
    }

    public String put(String key, String value) {

        // key原来不存在
        if (map.get(key) == null) {
            // 达到内存限制，则先淘汰一个尾部节点
            if (map.size() >= limit) {
                // 淘汰一个尾部节点
                Node t = tail;
                map.remove(t.key);
                tail = t.last;
                // help gc
                t.last = null;
            }

            Node node = new Node(key, value);
            // 保存到hash表并添加到链表头节点
            map.put(key, node);
            // lru链表还没添加过元素
            if (head == null) {
                head = node;
                tail = node;
            } else {
                node.next = head;
                head.last = node;
                head = node;
            }
        } else {
            // key已经存在，则将该node移动到链表头部
            Node node = map.get(key);
            // 将该节点的上一个节点和下一个节点连接起来
            Node last = node.last;
            Node next = node.next;
            last.next = next;
            next.last = last;
            // 将该节点重新放置到头节点
            node.next = head;
            head.last = node;
            node.last = null;
            // 重新移动头节点
            head = node;
        }

        return value;
    }

    /**
     * 删除一个节点
     */
    public boolean delete(String key) {
        if (key == null || map.get(key) == null) {
            return true;
        }

        Node node = map.get(key);
        map.remove(key);
        // 从链表中删除
        Node last = node.last;
        Node next = node.next;
        last.next = next;
        next.last = last;

        return true;
    }

    /**
     * 通过key获取该节点的值
     */
    public String get(String key) {
        if (key == null || map.get(key) == null) {
            return null;
        }
        Node node = map.get(key);
        Node last = node.last;
        Node next = node.next;
        last.next = next;
        next.last = last;
        // 放入到链表头
        head.last = node;
        node.next = head;
        node.last = null;
        head = node;
        return node.value;
    }

    /**
     * 节点
     */
    static class Node {
        public String value;
        public String key;
        public Node next;
        public Node last;

        public Node(String value, String key) {
            this.value = value;
            this.key = key;
        }
    }
}
